package heyuanyuan;

import java.util.Scanner;

// 循环队列实现
class PascalTriangleQueue {
    private int[] data;     // 存储队列元素的数组
    private int front;      // 队头指针
    private int rear;       // 队尾指针
    private int capacity;   // 队列容量

    // 构造函数
    public PascalTriangleQueue(int size) {
        this.capacity = size + 1; // 多留一个空位用于判断队满
        this.data = new int[this.capacity];
        this.front = 0;
        this.rear = 0;
    }

    // 入队操作
    public void enqueue(int value) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }
        data[rear] = value;
        rear = (rear + 1) % capacity; // 循环移动
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int value = data[front];
        front = (front + 1) % capacity; // 循环移动
        return value;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

// 杨辉三角生成器
public class YangHuiSanJiao {
    // 生成并打印杨辉三角
    public static void printPascalTriangle(int rows) {
        if (rows <= 0) {
            System.out.println("行数必须大于0");
            return;
        }

        PascalTriangleQueue queue = new PascalTriangleQueue(rows + 2);

        // 打印第一行
        printLine(rows, 1, "1");
        if (rows == 1) return;

        // 初始化第二行
        queue.enqueue(1);
        queue.enqueue(1);

        // 生成后续行
        for (int currentRow = 2; currentRow <= rows; currentRow++) {
            StringBuilder line = new StringBuilder();
            line.append("1 "); // 每行开头都是1

            int prev = queue.dequeue(); // 取出前一个数

            // 计算中间数字
            for (int j = 0; j < currentRow - 2; j++) {
                int curr = queue.dequeue();
                int sum = prev + curr;
                line.append(sum).append(" ");
                queue.enqueue(sum);
                prev = curr;
            }

            line.append("1"); // 每行结尾都是1
            queue.enqueue(1); // 存入最后一个1

            // 打印当前行
            printLine(rows, currentRow, line.toString());
        }
    }

    // 打印带缩进的行
    private static void printLine(int totalRows, int currentRow, String content) {
        // 计算缩进空格数
        int indent = 2 * (totalRows - currentRow);
        System.out.print(" ".repeat(indent));
        System.out.println(content);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入要打印的杨辉三角行数：");
        int rows = scanner.nextInt();

        printPascalTriangle(rows);

        scanner.close();
    }
}